package LeetCode._01算法入门.day08广度深度优先搜索;

import org.junit.Test;
import utils.MyPrintUtil;

/**
 * @author 挚爱之夕
 * @date 2022-02-27 - 02 - 27 - 16:28
 * @Description 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。
 * 填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，
 * 则将next指针设置为NULL。初始状态下，所有next指针都被设置为NULL。
 * @Version 1.0
 */
public class _116完美二叉树的同层 {
    /*
                    1
                  2   3
                4   5   6
              7   8   9  10
     -----------------------------------
                    1
                  2-->3
                4-->5-->6
              7-->8-->9-->10
     */
    static Node root = new Node(1);
    static {
        init();
    }
    public static void init(){
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        //第2层
        root.left = node2;
        root.right = node3;

        node2.next = node3;
        //第3层
        node2.left = node4;
        node2.right = node5;
        node3.left = node5;
        node3.right = node6;

        node4.next = node5;
        node5.next = node6;
        //第4层
        node4.left = node7;
        node4.right = node8;
        node5.left = node8;
        node5.right = node9;
        node6.left = node9;
        node6.right = node10;

        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
    }
    //by me
    @Test
    public void solve(){
        connect(root);
        MyPrintUtil.printPerfectTree(root);
    }

    public Node connect(Node root) {
        //结束条件
        if(root == null || root.left == null)//有左节点就有右节点
            return root;
        Node leftNode = root.left;
        Node rightNode = root.right;
        //连接左右 节点
        leftNode.next = rightNode;

        //相邻之间的连接：站在当前层，看下下层
        if(leftNode.right == null)
            return root;
        leftNode.right.next = rightNode.left;

        if(rightNode.next != null)
            rightNode.right.next = rightNode.next.left;
        //递归
        connect(leftNode);
        connect(rightNode);
        return root;
    }

    //官方思路
    public Node connect1(Node root) {
        if (root == null) {
            return null;
        }

        // 从根节点开始
        Node leftmost = root;

        while (leftmost.left != null) {

            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;

            while (head != null) {

                // CONNECTION 1
                head.left.next = head.right;

                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }

                // 指针向后移动
                head = head.next;
            }

            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }

        return root;
    }
}
